package clustering.streamming;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import preprocess.XMLDoc;

import similarity.Similarity;

public class KMediansClustering
{
    private static int MAX_CLUSTER_TIMES = 10;
    private Similarity similarity;

    public KMediansClustering(Similarity similarity)
    {
        super();
        this.similarity = similarity;
    }

    public List<List<Cluster>> cluster(List<Cluster> list, int count)
    {
        if (list.size() <= count)
        {
            List<List<Cluster>> result = new ArrayList<List<Cluster>>();
            for (Cluster clu : list)
            {
                List<Cluster> li = new ArrayList<Cluster>();
                li.add(clu);
                result.add(li);
            }
            return result;
        }
        List<List<Cluster>> clu = pickRandomCenters(list, count);
        List<List<Cluster>> newClu = clu;
        List<Cluster> centers = getCenters(clu);
        String keys = centers.toString();
        int times = 0;
        for (times = 0; times < MAX_CLUSTER_TIMES; times++)
        {
            clu = newClu;
            // 一次划分聚类
            for (Cluster doc : list)
            {
                boolean isCenter = false;
                int cluster = -1;
                double maxSimilarity = -1;
                for (int i = 0; i < centers.size(); i++)
                {
                    if (doc.equals(centers.get(i)))
                    {
                        isCenter = true;
                        break;
                    }
                    double similarity = this.similarity.calcSimilarity(doc
                            .getCenter(), centers.get(i).getCenter());
                    if (similarity > maxSimilarity)
                    {
                        maxSimilarity = similarity;
                        cluster = i;
                    }
                }
                if (!isCenter)
                {
                    clu.get(cluster).add(doc);
                }
            }

            newClu = calculateCenters(clu);
            centers = getCenters(newClu);
            String newKey = centers.toString();
            if (newKey.equals(keys))
            {
                break;
            }
            else
            {
                keys = newKey;
            }
        }
        return clu;
    }

    private List<Cluster> getCenters(List<List<Cluster>> lists)
    {
        List<Cluster> centers = new ArrayList<Cluster>();
        for (List<Cluster> l : lists)
        {
            centers.addAll(l);
        }
        return centers;
    }

    private List<List<Cluster>> pickRandomCenters(List<Cluster> list, int count)
    {
        List<List<Cluster>> result = new ArrayList<List<Cluster>>();
        int total = list.size();
        int splitter = total / count;
        Random rand = new Random(System.currentTimeMillis());
        for (int i = 0; i < count; i++)
        {
            int pos = rand.nextInt(splitter) + i * splitter;
            List<Cluster> l = new ArrayList<Cluster>();
            l.add(list.get(pos));
            result.add(l);
        }
        return result;
    }

    /*
     * remove all elements from clusters except the new centers of the cluster
     */
    private List<List<Cluster>> calculateCenters(List<List<Cluster>> lists)
    {
        List<List<Cluster>> result = new ArrayList<List<Cluster>>();
        for (List<Cluster> list : lists)
        {
            Cluster center = getCenter(list);
            List<Cluster> l = new ArrayList<Cluster>();
            l.add(center);
            result.add(l);
        }
        return result;
    }

    /*
     * return the center of the specified cluster
     */
    public Cluster getCenter(List<Cluster> list)
    {
        Cluster result = null;
        double distanceSum = Double.MAX_VALUE;
        for (Cluster center : list)
        {
            double sum = 0;
            double centerWeight = center.getWeight();
            XMLDoc centerDoc = center.getCenter();
            for (Cluster clu : list)
            {
                double distance = 1 - similarity.calcSimilarity(centerDoc, clu
                        .getCenter());
                distance *= (centerWeight * clu.getWeight());
                sum += distance * distance;
            }
            if (sum < distanceSum)
            {
                distanceSum = sum;
                result = center;
            }
        }
        return result;
    }

    /**
     * @return the similarity
     */
    public Similarity getSimilarity()
    {
        return similarity;
    }

    /**
     * @param similarity
     *            the similarity to set
     */
    public void setSimilarity(Similarity similarity)
    {
        this.similarity = similarity;
    }
}
